#define _CRT_SECURE_NO_WARNINGS 1

#include "queue.h"

int capital_lower(char x, char y)
{
	return abs((int)x - (int)y) == 32;
}

int delconstcaplow(char* s)
{
	int arrofsub[100] = { 0 };
	char str[100] = { 0 };
	size_t len = strlen(s);
	if (len == 1)
	{
		return s;
	}
	int i = 0;
	int j = 1;
	int flag = 0;
	int flag1 = 0;
	int k = 0;
	int count = 0;
	while (j < len)
	{
		flag = capital_lower(s[i], s[j]);
		if (flag)
		{
			arrofsub[k++] = i;
			i += 2;
			j += 2;
			count++;
			flag1 = 1;
		}
		else
		{
			i++;
			j++;
		}
	}
	i = 0;
	j = 0;
	k = 0;
	while (i < len)
	{
		if ((i == arrofsub[k]) && flag1)
		{
			i += 2;
			k++;
		}
		else
		{
			str[j++] = s[i++];
		}
	}
	i = 0;
	while (i < len - (count * 2))
	{
		s[i] = str[i];
		i++;
	}
	s[len - (count * 2)] = '\0';
	return flag1;
}

char* makeGood(char* s) {
	if (*s == '0')
	{
		return NULL;
	}
	int len = strlen(s);
	int flag = delconstcaplow(s);
	int i = 0;
	while (i < len)
	{
		if (flag == 0)
		{
			break;
		}
		else
		{
			flag = delconstcaplow(s);
		}
		i++;
	}
	return s;
}

void prevtraversal(TNode* root, int* arr, int* pcount)
{
	if (root == NULL)
		return;
	arr[(*pcount)++] = root->val;
	prevtraversal(root->left, arr, pcount);
	prevtraversal(root->right, arr, pcount);
}

int findint(int* difcolor, int size, int x)
{
	for (int i = 0; i < size; i++)
	{
		if (difcolor[i] == x)
			return 0;
	}
	return 1;
}

int numColor(struct TreeNode* root)
{
	int arr[1000] = { 0 };
	int difcolor[1000] = { 0 };
	int count = 0;
	int k = 1;
	int flag = 0;
	prevtraversal(root, arr, &count);
	difcolor[0] = arr[0];
	for (int i = 1; i < count; i++)
	{
		flag = findint(difcolor, k, arr[i]);
		if (flag)
			difcolor[k++] = arr[i];
	}
	return k;
}